﻿#define _CRT_SECURE_NO_WARNINGS 1
//递归的使用，函数自身调用自己

//stack overflow,为栈溢出
//把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再
//被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。
#include <stdio.h>
//计算n 的阶乘
/*int Fact(int n)
{
	if (n == 0)
		return 1;
	else
		return n * Fact(n - 1);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int r = Fact(n);
	printf("%d", r);
	return 0;
}*///递归

//迭代
//int Fact(int n)
//{
//	int r = 1;
//	
//	while (n)
//	{
//		
//		r *= n;
//		n--;
//	}
//	return r;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int r = Fact(n);
//	printf("%d", r);
//	return 0;
//}

//递归是大事化小，

//汉诺塔问题；有点类似斐波那契问题
//进行2的n次方-1；
//void move(char pos1, char pos2)
//{
//	printf(" %c->%c ", pos1, pos2);
//}
////n为盘子个数，pos1为起始位置，pos2为中转位置，pos3为目的位置
//void Hanoi(int n, char pos1, char pos2, char pos3)
//{
//	if (n == 1)
//	{
//		move(pos1, pos3);//最后一个直接放到第三个
//	}
//	else
//	{
//		Hanoi(n - 1, pos1, pos3, pos2);//递归，pos1中，通过pos3移动到pos2上
//		move(pos1, pos3);//移完n-1个了，把pos1上的转到pos3上
//		Hanoi(n - 1, pos2, pos1, pos3);//把pos2上的n-1个数通过pos1转到pos3上
//		//这里的第一个形参为起始位置，中转位置，目的位置
//	}
//}
//
//int main()
//{
//	Hanoi(1, 'A', 'B', 'C');//传进去三个棋盘
//	printf("\n");
//	Hanoi(3, 'A', 'B', 'C');
//	printf("\n");
//	Hanoi(4, 'A', 'B', 'C');
//	printf("\n");
//
//}


//顺序打印1234
//void print(int n)
//{
//	if (n > 9)
//	{
//		print(n / 10);//大事化小的作用
//	}
//	printf("%d ", n % 10);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	 print(n);
//	
//	return 0;
//}


//fib数列
//公式fib(n) = fib(n - 1) + fib(n - 2);
//int Fib(int n)
//{
//	if (n <= 2)
//	{
//		return 1;
//	}
//	else
//	{
//		return Fib(n - 1) + Fib(n - 2);
//	}
//}
//
//int main()
//{222222222222222222222222
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fib(n);
//	printf("%d", ret);
//	return 0;
//}
//递归太过深，时间过久；使用迭代更好


//int Fib(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n > 2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		n--;
//	}
//	return c;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fib(n);
//	printf("%d", ret);
//	return 0;
//}
